<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2158：Crash 的旅行计划</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Crash 的旅行计划</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Crash 的旅行计划</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Crash 的旅行计划                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：259MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>过不了多久，Crash 就要迎来他朝思暮想的暑假。在这个暑假里，他计划着到火星上旅游。在火星上有N 个旅游景点，Crash 用1 至N 这N 个正整数对这些景点标号。旅游景点之间通过双向道路相连。由于火星的环境和地球有很大的差异，建立道路的成本也相对较高。为了节约成本，只有N-1 条道路连接着这些旅游景点，不过可以保证任何两个不同的旅游景点都通过路径相连。 Crash 预先在互联网上查阅了这些景点的信息，根据网上的介绍，他对每个景点都有一个印象值，这个印象值为一个整数。在这个旅行中，他会选择一个景点作为旅行的开始，并沿着存在的道路到达其他景点游玩。为了使旅行不显得乏味，Crash 不会经过同一个景点超过一次。Crash 还给这次旅行定义了一个快乐指数，也就是他经过的所有景点的印象值之和。不过Crash 是个奇怪的小朋友，他对于景点的印象值会发生改变，并且他也没有决定好应该从哪个景点开始旅行。因此他希望你能写一个程序帮他完成一个简单的任务：根据当前他对每个景点的印象值，计算从某个景点开始旅行所能获得的最大的快乐指数。</p></p><hr/><h3>输入格式</h3><p><p>输入的第一行包含一个字符和一个正整数N，字符为ABC 中的一个，用来表示这个测试数据的类型（详见下面的数据规模和约定）。第二行包含N 个用空格隔开的整数，第i 个整数表示Crash 对i 号景点的初始印象值。接着有N-1 行，每行两个正整数a、b(1 &le; a, b &le; N)，表示从a 号景点到b 号景点有一条无向道路相连。最后是一些指令，指令只会是以下三种格式： 1．Change u x (1 &le; u &le; N) 将u 号景点的印象值修改为x。 2．Query u (1 &le; u &le; N) 询问从u 号景点开始能获得的最大的快乐指数。 3．Done 收到这个指令后，你的程序应该结束。</p></p><hr/><h3>输出格式</h3><p><p>对于每条Query 指令，输出对应的最大快乐指数。。</p></p><hr/><h3>样例输入</h3><pre>[样例输入1]
A 6
6 5 -4 3 -2 1
1 2
1 3
1 4
3 5
3 6
Query 3
Query 4
Change 6 10
Query 3
Change 2 -5
Query 3
Query 4
Done
[样例输入2]
B 5
5 -4 3 -2 1
1 2
2 3
3 4
4 5
Query 3
Change 5 10
Query 3
Query 2
Change 2 2
Query 3
Done</pre><hr/><h3>样例输出</h3><pre>[样例输出1]
7
14
7
6
15
[样例输出2]
4
11
7
11</pre><hr/><h3>提示</h3><p><p>测试数据分为ABC 三类，对于所有的测试数据都满足：在任何时候一个景点印象值的绝对值不超过10000，并且输入的道路一定能满足题目描述的要求，即使得任意两个不同的景点都能通过路径相连。对于A 类数据（占20%的分数）满足：N 和指令的条数都不超过1000。对于B 类数据（占40%的分数）满足：N 和指令的条数都不超过100000，且输入的第i 条道路，连接着i 号景点和i+1 号景点（详见样例2）。对于C 类数据（占40%的分数）满足：N 和指令的条数都不超过100000，且任何一个景点到1 号景点需要通过的道路条数不超过40。【特别说明】由于数据大小限制为5MB，我只好对测试时的输入文件进行压缩处理。下面的函数可以将压缩的输入文件转化为原始输入文件。（函数从infile 中读入压缩的输入文件，将解压缩后的输入文件输出到outfile 中） C/C++版本： void Uncompress(FILE *infile, FILE *outfile) { int N, M, L, now, A, B, Q, tmp, i; char type = getc(infile); fscanf(infile, &quot;%d%d%d&quot;, &amp;N, &amp;M, &amp;L); fscanf(infile, &quot;%d%d%d%d&quot;, &amp;now, &amp;A, &amp;B, &amp;Q); fprintf(outfile, &quot;%c %d\n&quot;, type, N); for (i = 1; i &lt;= N; i ++) { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 &lt; Q) tmp *= -1; if (i &lt; N) fprintf(outfile, &quot;%d &quot;, tmp); else fprintf(outfile, &quot;%d\n&quot;, tmp); } for (i = 1; i &lt; N; i ++) { now = (now * A + B) % Q; tmp = (i &lt; L) ? i : L; fprintf(outfile, &quot;%d %d\n&quot;, i - now % tmp, i + 1); } for (i = 1; i &lt; M; i ++) { now = (now * A + B) % Q; if (now * 3 &lt; Q) { now = (now * A + B) % Q; fprintf(outfile, &quot;Query %d\n&quot;, now % N + 1); } else { now = (now * A + B) % Q, tmp = now % 10000; now = (now * A + B) % Q; if (now * 2 &lt; Q) tmp *= -1; now = (now * A + B) % Q; fprintf(outfile, &quot;Change %d %d\n&quot;, now % N + 1, tmp); } } fprintf(outfile, &quot;Done\n&quot;); } Pascal 版本： procedure Uncompress(var infile, outfile : text); var N, M, L, now, A, B, Q, tmp, i : longint; ch : char; begin read(infile, ch, N, M, L, now, A, B, Q); writeln(outfile, ch, ' ', N); for i := 1 to N do begin now := (now * A + B) mod Q; tmp := now mod 10000; now := (now * A + B) mod Q; if now * 2 &lt; Q then tmp := -tmp; if i &lt; n then write(outfile, tmp, ' ') else writeln(outfile, tmp); end; for i := 1 to N - 1 do begin now := (now * A + B) mod Q; if i &lt; L then tmp := i else tmp := L; writeln(outfile, i - now mod tmp, ' ', i + 1); end; for i := 1 to M - 1 do begin now := (now * A + B) mod Q; if now * 3 &lt; Q then begin now := (now * A + B) mod Q; writeln(outfile, 'Query ', now mod N + 1); end else begin now := (now * A + B) mod Q; tmp := now mod 10000; now := (now * A + B) mod Q; if now * 2 &lt; Q then tmp := -tmp; now := (now * A + B) mod Q; writeln(outfile, 'Change ', now mod N + 1, ' ', tmp); end; end; writeln(outfile, 'Done'); end; 下面给出一个具体的例子。travel_compressed.in 表示压缩的输入文件， travel.in 表示解压缩后的输入文件。 travel_compressed.in travel.in A 5 7 3 17627 543 14278 380043 travel.in A 5 -4664 7653 -3584 -210 5852 1 2 1 3 2 4 3 5 Change 5 -3724 Query 4 Change 3 -5628 Query 2 Change 5 569 Query 5 Done</p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2158" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2158" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>